function match(str, pattern) {
  let M = pattern.length,
    N = str.length,
    i = 0,
    j = 0,
    o = {},
    dfa = KMP(pattern);
  //生成pattern中不重复元素的对象
  for (let t of pattern) {
    if (!o[t]) o[t] = t;
  }

  for (; i < N && j < M; i += 1) {
    j = !!o[str[i]] ? dfa[j][str[i]] : 0;
  }
  if (j === M) return true;
  return false;
}

function KMP(pattern) {
  let X = 0,
    R = 256,
    M = pattern.length,
    o = {},
    dfa = new Array(M);

  //生成pattern中不重复元素的对象
  for (let t of pattern) {
    if (!o[t]) o[t] = t;
  }

  //创建长度为dfa.length的数组，每一项为一个对象
  for (let i = 0; i < dfa.length; i += 1) dfa[i] = {
    ...o
  };

  //初始化dfa[0],即初始的X状态，后面的状态要用这一状态来复制
  for (let k in dfa[0]) {
    dfa[0][k] = 0;
  }
  //状态0时匹配到第一位总是进入状态1
  dfa[0][pattern[0]] = 1;

  //生成后面的状态机
  for (let j = 1; j < M; j += 1) {
    for (let c in o) {
      //设置状态j的匹配失败项，从状态X复制
      dfa[j][c] = dfa[X][c];
    }
    //设置匹配成功项
    dfa[j][pattern[j]] = j + 1;
    //计算下一状态的 X
    X = dfa[X][pattern[j]];

  }
  return dfa;
}

console.log(match('asdfasdfsafabababafabababacasdf', 'ababac'));